/*
 * round1.cpp
 *
 *  Created on: May 21, 2011
 *      Author: Zeng
 */

#include <algorithm>
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <string.h>
#include "round1.h"

using namespace std;

void rpi() {
	int case_num, line_num;
	cin >> case_num;

	for (int i = 0; i < case_num; ++i) {
		cin >> line_num;
		string match[line_num];
		double wp[line_num], owp[line_num], oowp[line_num];
		memset(wp, 0, sizeof(double)*line_num);
		memset(owp, 0, sizeof(double)*line_num);
		memset(oowp, 0, sizeof(double)*line_num);

		// wp
		for (int j = 0; j < line_num; ++j) {
			cin >> match[j];
			double count = 0;
			string team = match[j];
			for (int x = 0; x < (int)team.length(); ++x) {
				if (team[x] != '.') {
					wp[j] += (team[x] == '1') ? 1 : 0 ;
					count++;
				}
			}
			if (count > 0) wp[j] /= count;
		}

		// owp
		for (int row = 0; row < line_num; ++row) {
			string team = match[row];
			double count = 0;
			for (int col = 0; col < (int)team.length(); ++col) {
				if (team[col] != '.' && col != row) {
					double one_wp, one_count;
					one_wp = one_count = 0;
					for (int crow = 0; crow < line_num; ++crow) {
						if (crow != row && (match[crow])[col] != '.') {
							one_wp += ((match[crow])[col] == '1') ? 0 : 1;
							one_count++;
						}
					}
					if (one_count > 0) one_wp /= one_count;
					count++;
					owp[row] += one_wp;
				}
			}
			if (count > 0) owp[row] /= count;
		}

		// oowp
		for (int row1 = 0; row1 < line_num; ++row1) {
			string team = match[row1];
			double count = 0;
			for (int col1 = 0; col1 < (int)team.length(); ++col1) {
				if (team[col1] != '.' && col1 != row1) {
					oowp[row1] += owp[col1];
					count++;
				}
			}
			if (count > 0) oowp[row1] /= count;
		}

		// rpi
		cout << "Case #" << i+1 << ":" << endl;
		for (int row2 = 0; row2 < line_num; ++row2) {
			double rpi = 0.25 * wp[row2] + 0.5 * owp[row2] + 0.25 * oowp[row2];
			cout << rpi << endl;
		}
	}
}

void hotdogs() {
	const double EPSILON = 1e-6;
	int case_num, line_num, min_dist;
	cin >> case_num;

	for (int i = 0; i < case_num; ++i) {
		cin >> line_num;
		cin >> min_dist;

		// read the positions
		pair< int, int > vendors[line_num]; // <pos, number>
		for (int j = 0; j < line_num; ++j) {
//			cin >> vendors[j].first >> vendors[j].second;
//			scanf("%d%d",&vendors[j].first,&vendors[j].second);
			int x, m;
			cin >> x >> m;
			vendors[j] = make_pair(x, m);
//			cout << vendors[j].first << "  " << vendors[j].second << endl;
		}
		sort(vendors, vendors+line_num);

		// binary search to get the solution
		double low, high, mid;
		low = 0;
		high = 1e15;
		int count = 0;
//		while (high - low > (high * EPSILON)) {
//		while (high - low > (EPSILON)) {
		while (count < 100) {
			mid = (high + low) / 2;

			bool valid = true;
			double cur = -1e15;
			for (int j = 0; j < line_num; ++j) {
				double left = vendors[j].first - mid;
				double right = vendors[j].first + mid;
				double cur_r = max(left, cur+min_dist) + (double)((long long)(vendors[j].second - 1) * (long long)min_dist);
				if (cur_r > right) {
					valid = false;
					break;
				}
				cur = cur_r;
			}
			if (valid) high = mid;
			else low = mid;

			count++;
		}

		cout << "Case #" << i+1 << ": " << mid << endl;
	}
}
